package IndexComponent;

import java.nio.ByteBuffer;
import java.util.*;

import PagedFile.Buffer;
import PagedFile.PF_Abort_Exception;
import PagedFile.PF_FileHandle;
import RecordManagement.RID;

/*
 * A B+-Tree Node is supposed to fullize a block in the file, i.e. 4096 Bytes.
 * A B+-Tree Node has the following properties:
 * 1. A node is a leaf or an internal node;
 * 2. Data items are stored at leaves;
 * 3. The root either is a leaf or has between 2 and M children(i.e. 1 to M-1 keys)
 * 4. An internal node store up to M-1 keys to guide searching;
 *    key i represents the smallest key in subtree i+1;
 * 5. All non-leaf nodes, except the root, have between M/2 and M children.(i.e. M/2-1 to M-1 keys)
 * 6. All leaves, except the root, are at the same depth,
 *    and have between L/2 and L data items.
 * A stored node structure is as follows:
 * size/byte(s)	contents
 * 	1			leaf or internal node
 * 	4			page number
 * 	4			number of valid keyword
 * 	4			previous leaf/node page number
 * 	4			next leaf page/node number
 * 	(sizeof(keyword) + sizeof(data item))*L	data items array
 * 	if an internal node
 * 	(sizeof(pointer) + sizeof(keyword)) * M + sizeof(pointer) data item and pageNum array
 */
public class BPlusTreeNode {
	
	static final int NULL = -1; //null pointer in a node pointer array.
	public static final int PAGEHEADSIZE = 20;
	
	/* Tyep information */
	byte type = LEAF;
	public static final byte LEAF = (byte)0xff;
	public static final byte NODE = (byte)0x00;
		
	/* Global properties */
	BPTree_FileHead fhead;
	final static int DataLength = RID.STORELENGTH;
	
	/* Local properties */
	int pageNum;
	int numOfKeyword;
	int prePageNum;
	int nextPageNum;
	
	private final static int KEYNUMOFFSET = 5;
	private final static int PRENODEOFFSET = 9;
	private final static int NEXTNODEOFFSET = 13;	
	
	PF_FileHandle pfh;
	List<Keyword> keyword = null;
	List<Integer> pointer = null;
	List<RID> dataItem = null;
	
	//Construct a New Tree Node
	public BPlusTreeNode(PF_FileHandle pfh, BPTree_FileHead ixFileHead, byte type) {
		this.fhead = ixFileHead;
		this.pfh = pfh;
		
		this.type = type;
		numOfKeyword = 0;
		prePageNum = 0;
		nextPageNum = 0;

		Buffer buf = pfh.AllocatePage();
		ByteBuffer bb = buf.contents;
		
		pageNum = buf.block.pageNum;

		buf.mark(this.hashCode());
		bb.position(0);
		bb.put(type);
		bb.putInt(pageNum);
		bb.putInt(numOfKeyword);
		bb.putInt(prePageNum);
		bb.putInt(nextPageNum);
		pfh.UnpinPage(pageNum);
	}
	
	//Load a Tree Node From the Disk, and Construct it in memory.
	public BPlusTreeNode(BPTree_FileHead ixFileHead, PF_FileHandle pfh, int pageNum) throws PF_Abort_Exception {
		this.fhead = ixFileHead;
		this.pfh = pfh;
		
		Buffer buf = pfh.GetThisPage(pageNum);
		ByteBuffer bb = buf.contents;
		bb.position(0);
		type = bb.get();
		this.pageNum = bb.getInt();
		if (this.pageNum != pageNum)
			throw new IX_Abort_Exception("Fatal");
		numOfKeyword = bb.getInt();
		prePageNum = bb.getInt();
		nextPageNum = bb.getInt();

		pfh.UnpinPage(pageNum);
	}
		
	public Keyword GetKeyword(int index) throws PF_Abort_Exception {
		if (index >= numOfKeyword)
			throw new IX_Abort_Exception("Index Out of Bound");
		
		if (keyword != null)
			return keyword.get(index);

		Buffer buf = pfh.GetThisPage(pageNum);
		if (type == LEAF)
			buf.contents.position(PAGEHEADSIZE+index*(fhead.KeywordLength+RID.STORELENGTH));
		else if (type == NODE)
			buf.contents.position(PAGEHEADSIZE+4+index*(fhead.KeywordLength+4));
		Keyword ret=null;
		if (fhead.KeywordType == Keyword.KEYTYPEINT) 
			ret = new IntKeyword(buf.contents.getInt());
		else if (fhead.KeywordType == Keyword.KEYTYPESTRING) {
			byte[] temp = new byte[fhead.KeywordLength];
			buf.contents.get(temp);
			ret = new StringKeyword(temp, fhead.KeywordLength);
		}
		pfh.UnpinPage(buf.block.pageNum);
		return ret;
		
	}
	
	public void SetKeyword(int index, Keyword key) {
		if (index >= numOfKeyword)
			throw new IX_Abort_Exception("Index Out of Bound");
		
		if (keyword!=null)
			keyword.set(index, key);
		
		Buffer buf = pfh.GetThisPage(pageNum);
		buf.mark(this.hashCode());
		if (type == LEAF)
			buf.contents.position(PAGEHEADSIZE+index*(fhead.KeywordLength+RID.STORELENGTH));
		else if (type == NODE)
			buf.contents.position(PAGEHEADSIZE+4+index*(fhead.KeywordLength+4));
		if (fhead.KeywordType == Keyword.KEYTYPEINT)
			buf.contents.putInt(((IntKeyword)key).getValue());
		else if (fhead.KeywordType == Keyword.KEYTYPESTRING)
			buf.contents.put(((StringKeyword)key).getBytes());
		pfh.UnpinPage(buf.block.pageNum);

	}
	
	public int GetPointer(int index) throws PF_Abort_Exception {
		if (index > numOfKeyword)
			throw new IX_Abort_Exception("Index Out of Bound");
		
		if (pointer != null)
			return pointer.get(index);

		Buffer buf = pfh.GetThisPage(pageNum);
		int ret = buf.contents.getInt(PAGEHEADSIZE+index*(4+fhead.KeywordLength));
		pfh.UnpinPage(buf.block.pageNum);
		return ret;
		
	}
	
	public void SetPointer(int index, int pageNum) {
		if (index > numOfKeyword)
			throw new IX_Abort_Exception("Index Out of Bound");
		
		if (pointer != null)
			pointer.set(index, pageNum);
		
		Buffer buf = pfh.GetThisPage(this.pageNum);
		buf.mark(this.hashCode());
		buf.contents.putInt(PAGEHEADSIZE+index*(4+fhead.KeywordLength), pageNum);
		pfh.UnpinPage(buf.block.pageNum);
		
	}
	
	public RID GetDataItem(int index) throws PF_Abort_Exception {
		if (index >= numOfKeyword)
			throw new IX_Abort_Exception("Index Out of Bound");
		
		if (dataItem != null)
			return dataItem.get(index);
		
		Buffer buf = pfh.GetThisPage(pageNum);
		buf.contents.position(PAGEHEADSIZE+fhead.KeywordLength+ index*(RID.STORELENGTH+fhead.KeywordLength));
		RID ret = new RID(buf.contents.getInt(), buf.contents.getInt());
		pfh.UnpinPage(buf.block.pageNum);
		return ret;
		
	}
	
	public void SetDataItem(int index, RID rid) {
		if (index >= numOfKeyword)
			throw new IX_Abort_Exception("Index Out of Bound");
		
		if (dataItem != null)
			dataItem.set(index, rid);
		
		Buffer buf = pfh.GetThisPage(pageNum);
		buf.mark(this.hashCode());
		buf.contents.position(PAGEHEADSIZE+fhead.KeywordLength+ index*(RID.STORELENGTH+fhead.KeywordLength));
		buf.contents.putInt(rid.pageNum);
		buf.contents.putInt(rid.slotNum);
		pfh.UnpinPage(buf.block.pageNum);		
		
	}
	
	/* Pair Operation */
	public KeywordDataPair GetKeyDataPair(int index) throws PF_Abort_Exception {

		if (index >= numOfKeyword)
			throw new IX_Abort_Exception("Index Out of Bound");
		
		Buffer buf = pfh.GetThisPage(pageNum);
		buf.contents.position(PAGEHEADSIZE+index*(fhead.KeywordLength+RID.STORELENGTH));
		Keyword key;
		if (fhead.KeywordType == Keyword.KEYTYPEINT)
			key = new IntKeyword(buf.contents.getInt());
		else {
			byte[] temp = new byte[fhead.KeywordLength];
			buf.contents.get(temp);
			key = new StringKeyword(temp, fhead.KeywordLength);
		}
		RID rid = new RID(buf.contents.getInt(), buf.contents.getInt());
		pfh.UnpinPage(pageNum);
		return new KeywordDataPair(key, rid);
		
	}
	
/*	public void SetKeyDataPair(int index, KeywordDataPair kdp) {

		if (index >= numOfKeyword)
			throw new IX_Abort_Exception();
		
		Buffer buf = pfh.GetThisPage(pageNum);
		buf.mark(this.hashCode());
		buf.contents.position(PAGEHEADSIZE+index*(fhead.KeywordLength+RID.STORELENGTH));
		if (fhead.KeywordType == Keyword.KEYTYPEINT) 
			buf.contents.putInt(((IntKeyword)kdp.key).getValue());
		else
			buf.contents.put(((StringKeyword)kdp.key).getBytes());
		buf.contents.putInt(kdp.rid.pageNum);
		buf.contents.putInt(kdp.rid.slotNum);
		pfh.UnpinPage(pageNum);
		
	}
*/	
	public KeywordPointerPair GetKeyPointerPair(int index) throws PF_Abort_Exception {
		if (index >= numOfKeyword)
			throw new IX_Abort_Exception("Index Out of Bound");
		
		if (keyword != null && pointer != null)
			return new KeywordPointerPair(keyword.get(index),pointer.get(index));
		
		Buffer buf = pfh.GetThisPage(pageNum);
		buf.contents.position(PAGEHEADSIZE+4+index*(4+fhead.KeywordLength));
		Keyword key;
		if (fhead.KeywordType == Keyword.KEYTYPEINT) 
			key = new IntKeyword(buf.contents.getInt());
		else {
			byte[] temp = new byte[fhead.KeywordLength];
			buf.contents.get(temp);
			key = new StringKeyword(temp, fhead.KeywordLength);
		}
		int pointer = buf.contents.getInt();
		pfh.UnpinPage(pageNum);
		return new KeywordPointerPair(key, pointer);
		
	}
	
/*	public void SetKeyPointerPair(int index, KeywordPointerPair kpp) {
		if (index >= numOfKeyword)
			throw new IX_Abort_Exception();
		
		if (keyword != null)
			keyword.set(index, kpp.key);
		if (pointer != null)
			pointer.set(index, kpp.pointer);
		
		Buffer buf = pfh.GetThisPage(pageNum);
		buf.contents.position(PAGEHEADSIZE+4+index*(4+fhead.KeywordLength));
		buf.mark(this.hashCode());
		if (fhead.KeywordType == Keyword.KEYTYPEINT) 
			buf.contents.putInt(((IntKeyword)kpp.key).getValue());
		else
			buf.contents.put(((StringKeyword)kpp.key).getBytes());
		buf.contents.putInt(kpp.pointer);
		pfh.UnpinPage(pageNum);
		
	}
*/	
	public void AddKeyDataPair(KeywordDataPair kdp) throws PF_Abort_Exception {
		if (numOfKeyword == fhead.Level)
			throw new IX_Abort_Exception("Leaf Full");
		
		if (keyword != null)
			keyword.add(kdp.key);
		if (dataItem != null)
			dataItem.add(kdp.rid);

		Buffer buf = pfh.GetThisPage(pageNum);
		buf.contents.position(PAGEHEADSIZE+numOfKeyword*(fhead.KeywordLength+RID.STORELENGTH));
		buf.mark(this.hashCode());
		if (fhead.KeywordType == Keyword.KEYTYPEINT)
			buf.contents.putInt(((IntKeyword)kdp.key).getValue());
		else if (fhead.KeywordType == Keyword.KEYTYPESTRING )
			buf.contents.put(((StringKeyword)kdp.key).getBytes());
		buf.contents.putInt(kdp.rid.pageNum);
		buf.contents.putInt(kdp.rid.slotNum);
		++numOfKeyword;
		buf.contents.putInt(KEYNUMOFFSET,numOfKeyword);
		pfh.UnpinPage(pageNum);
	}
	
	void AddKeyPointerPair(KeywordPointerPair kpp) throws PF_Abort_Exception {
		if (numOfKeyword == fhead.Order)
			throw new IX_Abort_Exception("Node Full");
		
		if (keyword != null)
			keyword.add(kpp.key);
		if (pointer != null)
			pointer.add(kpp.pointer);

		Buffer buf = pfh.GetThisPage(pageNum);
		buf.contents.position(PAGEHEADSIZE + 4 + numOfKeyword*(fhead.KeywordLength+4));
		buf.mark(this.hashCode());
		if (fhead.KeywordType == Keyword.KEYTYPEINT)
			buf.contents.putInt(((IntKeyword)kpp.key).getValue());
		else if (fhead.KeywordType == Keyword.KEYTYPESTRING)
			buf.contents.put(((StringKeyword)kpp.key).getBytes());
		buf.contents.putInt(kpp.pointer);
		++numOfKeyword;
		buf.contents.putInt(KEYNUMOFFSET,numOfKeyword);
		pfh.UnpinPage(pageNum);
	}
	
	public void AddKeyDataPair(int index, KeywordDataPair kdp) throws PF_Abort_Exception {
		if (numOfKeyword == fhead.Level || index > numOfKeyword)
			throw new IX_Abort_Exception("Index Out of Bound");

		if (keyword != null)
			keyword.add(index, kdp.key);
		if (dataItem != null)
			dataItem.add(index, kdp.rid);
		
		Buffer buf = pfh.GetThisPage(pageNum);
		ByteBuffer bb = buf.contents;
		buf.mark(this.hashCode());
		
		byte[] temp = new byte[(fhead.KeywordLength+RID.STORELENGTH)*(numOfKeyword-index)];
		bb.position(PAGEHEADSIZE + index*(fhead.KeywordLength+RID.STORELENGTH));
		bb.get(temp);
		bb.position(PAGEHEADSIZE + (index+1)*(fhead.KeywordLength+RID.STORELENGTH));
		bb.put(temp);
		
		bb.position(PAGEHEADSIZE + index*(fhead.KeywordLength+RID.STORELENGTH));
		if (fhead.KeywordType == Keyword.KEYTYPEINT)
			bb.putInt(((IntKeyword)kdp.key).getValue());
		else if (fhead.KeywordType == Keyword.KEYTYPESTRING)
			bb.put(((StringKeyword)kdp.key).getBytes());
		bb.putInt(kdp.rid.pageNum);
		bb.putInt(kdp.rid.slotNum);
		
		++numOfKeyword;
		bb.putInt(KEYNUMOFFSET,numOfKeyword);
		
		pfh.UnpinPage(buf.block.pageNum);
	}

	public KeywordDataPair RemoveKeyDataPair(int index) {
		if (index >= numOfKeyword) 
			throw new IX_Abort_Exception("Index Out of Bound");
		
		if(keyword!=null)
			keyword.remove(index);
		if (dataItem!=null)
			dataItem.remove(index);
		
		Keyword retkey=null;
		RID retrid=null;
		
		Buffer buf = pfh.GetThisPage(pageNum);
		ByteBuffer bb = buf.contents;
		buf.mark(this.hashCode());
		bb.position(PAGEHEADSIZE + index*(fhead.KeywordLength+RID.STORELENGTH));
		
		if (fhead.KeywordType == Keyword.KEYTYPEINT) {
			retkey = new IntKeyword(bb.getInt());
		} else if (fhead.KeywordType == Keyword.KEYTYPESTRING) {
			byte[] temp = new byte[fhead.KeywordLength];
			bb.get(temp);
			retkey = new StringKeyword(temp, fhead.KeywordLength);
		}
		retrid = new RID(bb.getInt(), bb.getInt());
		
		byte[] temp = new byte[(fhead.KeywordLength+RID.STORELENGTH)*(numOfKeyword-index-1)];
		bb.position(PAGEHEADSIZE+(index+1)*(fhead.KeywordLength+RID.STORELENGTH));
		bb.get(temp);
		bb.position(PAGEHEADSIZE+index*(fhead.KeywordLength+RID.STORELENGTH));
		bb.put(temp);
		
		--numOfKeyword;
		bb.putInt(KEYNUMOFFSET, numOfKeyword);
		pfh.UnpinPage(buf.block.pageNum);
		
		return new KeywordDataPair(retkey, retrid);
	}
	
	public KeywordPointerPair RemoveKeyPointerPair(int index) {
		if (index >= numOfKeyword)
			throw new IX_Abort_Exception("Index Out of Bound");
		
		if (keyword!=null)
			keyword.remove(index);
		if (pointer!=null)
			pointer.remove(index+1);
		
		Keyword retkey=null;
		int retpointer=0;

		Buffer buf = pfh.GetThisPage(pageNum);
		ByteBuffer bb = buf.contents;
		buf.mark(this.hashCode());
		bb.position(PAGEHEADSIZE+4+index*(fhead.KeywordLength+4));
		
		if (fhead.KeywordType == Keyword.KEYTYPEINT) {
			retkey = new IntKeyword(bb.getInt());
		} else if (fhead.KeywordType == Keyword.KEYTYPESTRING) {
			byte[] temp = new byte[fhead.KeywordLength];
			bb.get(temp);
			retkey = new StringKeyword(temp, fhead.KeywordLength);
		}
		retpointer = bb.getInt();
		
		byte[] temp = new byte[(fhead.KeywordLength+4)*(numOfKeyword-index-1)];
		bb.position(PAGEHEADSIZE+4+(index+1)*(fhead.KeywordLength+4));
		bb.get(temp);
		bb.position(PAGEHEADSIZE+4+index*(fhead.KeywordLength+4));
		bb.put(temp);
		
		--numOfKeyword;
		bb.putInt(KEYNUMOFFSET, numOfKeyword);
		pfh.UnpinPage(buf.block.pageNum);
		
		return new KeywordPointerPair(retkey, retpointer);
	}
	
	public void AddKeyPointerPair(int index, KeywordPointerPair kpp) throws PF_Abort_Exception {
		if (numOfKeyword == fhead.Order || index > numOfKeyword)
			throw new IX_Abort_Exception("Index Out of Bound");
		
		if (keyword!=null)
			keyword.add(index,kpp.key);
		if (pointer!=null)
			pointer.add(index+1,kpp.pointer);

		Buffer buf = pfh.GetThisPage(pageNum);
		ByteBuffer bb = buf.contents;
		buf.mark(this.hashCode());
		
		byte[] temp = new byte[(fhead.KeywordLength+4)*(numOfKeyword-index)];
		bb.position(PAGEHEADSIZE+4+index*(fhead.KeywordLength+4));
		bb.get(temp);
		bb.position(PAGEHEADSIZE+4+(index+1)*(fhead.KeywordLength+4));
		bb.put(temp);
		
		bb.position(PAGEHEADSIZE+4+index*(fhead.KeywordLength+4));
		if (fhead.KeywordType == Keyword.KEYTYPEINT)
			bb.putInt(((IntKeyword)kpp.key).getValue());
		else if (fhead.KeywordType == Keyword.KEYTYPESTRING)
			bb.put(((StringKeyword)kpp.key).getBytes());
		bb.putInt(kpp.pointer);
		
		++numOfKeyword;
		bb.putInt(KEYNUMOFFSET,numOfKeyword);
		
		pfh.UnpinPage(buf.block.pageNum);
	}
	
	/* Interferencing Checking */
	public boolean isPredecessor(int pageNum, int prePageNum){

		List<Integer> pointer = LoadPointer();
				
		int index = pointer.indexOf(pageNum);
		if (index<1)
			return false;
		return pointer.get(index-1).intValue() == prePageNum;
	}
	
	public boolean CanCombine(BPlusTreeNode node) {
		if (node.type != type )
			return false;
		if ( type == LEAF )
			return node.numOfKeyword+numOfKeyword < fhead.Level;
		else
			return node.numOfKeyword+numOfKeyword+2 <= fhead.Order;
	}
		
	/* Return true if another leaf/dataItem can be inserted. */
	public boolean IsFull(){
		if (type == LEAF)
			return numOfKeyword==fhead.Level;
		return numOfKeyword+1==fhead.Order;
	}
	
	public List<Keyword> LoadKeyword() throws PF_Abort_Exception {
		if (keyword != null)
			return keyword;
		
		keyword = new ArrayList<Keyword>();
		Buffer buf = pfh.GetThisPage(pageNum);
		ByteBuffer bb = buf.contents;
		byte[] temp = null;
		if (type == LEAF) {
			if ( fhead.KeywordType == Keyword.KEYTYPEINT ) {
				for (int i=0; i<numOfKeyword; ++i)
					keyword.add(new IntKeyword(bb.getInt(PAGEHEADSIZE+i*(fhead.KeywordLength+RID.STORELENGTH))));
			} else if ( fhead.KeywordType == Keyword.KEYTYPESTRING ) {
				temp = new byte[fhead.KeywordLength];
				for (int i=0; i<numOfKeyword; ++i) {
					bb.position(PAGEHEADSIZE+i*(fhead.KeywordLength+RID.STORELENGTH));
					bb.get(temp);
					keyword.add(new StringKeyword(temp,fhead.KeywordLength));
				}
			}
		} else if (type == NODE) {
			if ( fhead.KeywordType == Keyword.KEYTYPEINT ) {
				for (int i=0; i<numOfKeyword; ++i)
					keyword.add(new IntKeyword(bb.getInt(PAGEHEADSIZE+4+i*(fhead.KeywordLength+4))));
			} else if ( fhead.KeywordType == Keyword.KEYTYPESTRING ) {
				temp = new byte[fhead.KeywordLength];
				for (int i=0; i<numOfKeyword; ++i) {
					bb.position(PAGEHEADSIZE+4+i*(fhead.KeywordLength+4));
					bb.get(temp);
					keyword.add(new StringKeyword(temp,fhead.KeywordLength));
				}
			}
		}
		pfh.UnpinPage(buf.block.pageNum);
		return keyword;
	}
	
	public List<RID> LoadData() throws PF_Abort_Exception {
		if (dataItem != null)
			return dataItem;
		
		dataItem = new ArrayList<RID>();
		Buffer buf = pfh.GetThisPage(pageNum);
		ByteBuffer bb = buf.contents;
		
		for (int i=0; i<numOfKeyword; ++i) {
			bb.position(PAGEHEADSIZE+fhead.KeywordLength+i*(fhead.KeywordLength+RID.STORELENGTH));
			dataItem.add(new RID(bb.getInt(), bb.getInt()));
		}
		
		pfh.UnpinPage(buf.block.pageNum);
		return dataItem;
	}
	
	private List<Integer> LoadPointer() throws PF_Abort_Exception {
		if (pointer != null)
			return pointer;
		
		pointer = new ArrayList<Integer>();
		
		Buffer buf = pfh.GetThisPage(pageNum);
		ByteBuffer bb = buf.contents;
		
		for (int i=0; i<=numOfKeyword; ++i) 
			pointer.add(bb.getInt(PAGEHEADSIZE+i*(4+fhead.KeywordLength)));
		
		pfh.UnpinPage(buf.block.pageNum);
		return pointer;
	}
	
	/* Leaf Operation */
	public void InsertIntoLeaf(Keyword key, RID rid) throws PF_Abort_Exception {
		List<Keyword> keyword = LoadKeyword();
		int i;
		
		for (i=0; i<keyword.size() && key.compareTo(keyword.get(i))>0; ++i);
		
		AddKeyDataPair(i, new KeywordDataPair(key, rid));
	}
	
	public BPlusTreeNode InsertIntoNode(int leftChild, Keyword key, int rightChild, List<BPlusTreeNode> parentList) throws PF_Abort_Exception {
		/* There are 3 situations here:
		 * 1. There is space in the node, just insert the pointer and keyword.
		 * 2. There is no space in the node, and this node is root, splite it and set new root.
		 * 3. There is no space in the node, and is a normal internal node, call this method recursively.
		 */
		List<Integer> pointer = LoadPointer();
		int i;
		if (!IsFull()) { //Condition 1
			i = pointer.indexOf(leftChild);
			if (i<0)
				throw new IX_Abort_Exception("Pointer Not Exists");
			AddKeyPointerPair(i, new KeywordPointerPair(key, rightChild));
			return null;
		}
		
		//Condition 2,3
		BPlusTreeNode anotherNode = new BPlusTreeNode(pfh, fhead, NODE);
		Keyword KeyInsertedIntoParent = InsertAndSpliteNode(leftChild, key, rightChild, anotherNode);
		
		if (parentList.size()==0) { //this node is root
			BPlusTreeNode newRoot = new BPlusTreeNode(pfh, fhead, NODE);
			newRoot.SetPointer(0, pageNum);
			newRoot.AddKeyPointerPair(new KeywordPointerPair(KeyInsertedIntoParent, anotherNode.pageNum));
			return newRoot;
		} else { //this node is a normal internal node.
			BPlusTreeNode parent = parentList.get(parentList.indexOf(this)-1);
			
			return parent.InsertIntoNode(pageNum, KeyInsertedIntoParent, anotherNode.pageNum, parentList);
		}
	}
	
	public KeywordDataPair DeleteFromLeaf(Keyword key, RID rid) throws PF_Abort_Exception {
		int i = LoadData().indexOf(rid);
		if (i<0)
			return null;
		return RemoveKeyDataPair(i);
	}
	
	public KeywordDataPair DeleteFromLeaf(int index) {
		return RemoveKeyDataPair(index);
	}
	
	public Keyword InsertAndSpliteLeaf(Keyword key, RID rid, BPlusTreeNode node) throws PF_Abort_Exception {
		if (type != LEAF || node.type != LEAF || node.numOfKeyword != 0)
			throw new IX_Abort_Exception("Can not Insert And Splite");
		
		List<Keyword> keyword = LoadKeyword();
		List<RID> dataItem = LoadData();
		int i;
		
		for (i=0; i<keyword.size() && key.compareTo(keyword.get(i))>0; ++i);
		
		keyword.add(i, key);
		dataItem.add(i, rid);
		++numOfKeyword;

		int suckPosition = fhead.Level/2+1;
		Keyword ret = keyword.get(suckPosition);
		
		int numOfKeyInAnother = numOfKeyword-suckPosition;
		int preNextPageNum = nextPageNum;
		numOfKeyword -= numOfKeyInAnother;
		Buffer buf = pfh.GetThisPage(pageNum);
		ByteBuffer bb = buf.contents;
		buf.mark(this.hashCode());
		if (i<suckPosition) {
			byte[] temp = new byte[(fhead.KeywordLength+RID.STORELENGTH)*(suckPosition-i)];
			bb.position(PAGEHEADSIZE+(fhead.KeywordLength+RID.STORELENGTH)*i);
			bb.get(temp);
			bb.position(PAGEHEADSIZE+(fhead.KeywordLength+RID.STORELENGTH)*(i+1));
			bb.put(temp);
			bb.position(PAGEHEADSIZE+(fhead.KeywordLength+RID.STORELENGTH)*i);
			if (fhead.KeywordType==Keyword.KEYTYPEINT)
				bb.putInt(((IntKeyword)key).getValue());
			else if (fhead.KeywordType==Keyword.KEYTYPESTRING)
				bb.put(((StringKeyword)key).getBytes());
			bb.putInt(rid.pageNum);
			bb.putInt(rid.slotNum);
		}
		nextPageNum = node.pageNum;
		bb.putInt(NEXTNODEOFFSET, nextPageNum);
		bb.putInt(KEYNUMOFFSET, numOfKeyword);
		pfh.UnpinPage(pageNum);
		node.SetPrePageNum(pageNum);
		if (preNextPageNum != 0) {
			BPlusTreeNode preNextLeaf = new BPlusTreeNode(fhead, pfh, preNextPageNum);
			preNextLeaf.SetPrePageNum(nextPageNum);
			preNextLeaf = null;
			node.SetNextPageNum(preNextPageNum);
		}
		
		for (i=0; i<numOfKeyInAnother; ++i)
			node.AddKeyDataPair(
					new KeywordDataPair(keyword.remove(suckPosition),
							dataItem.remove(suckPosition) )
					);
		
		return ret;
	}
	
	public void SetPrePageNum(int prePageNum) throws PF_Abort_Exception {
		Buffer buf = pfh.GetThisPage(pageNum);
		buf.mark(this.hashCode());
		buf.contents.putInt(PRENODEOFFSET, prePageNum);
		pfh.UnpinPage(pageNum);
		this.prePageNum = prePageNum;
	}
	
	public void SetNextPageNum(int nextPageNum) throws PF_Abort_Exception {
		Buffer buf = pfh.GetThisPage(pageNum);
		buf.mark(this.hashCode());
		buf.contents.putInt(NEXTNODEOFFSET, nextPageNum);
		pfh.UnpinPage(pageNum);
		this.nextPageNum = nextPageNum;
	}
	
	public Keyword InsertAndSpliteNode(int lp, Keyword key, int rp, BPlusTreeNode node) throws PF_Abort_Exception {
		if (type != NODE || node.type != NODE || node.numOfKeyword != 0)
			throw new IX_Abort_Exception("Can not Insert and Splite");
		
		List<Keyword> keyword = LoadKeyword();
		List<Integer> pointer = LoadPointer();
		int i = pointer.indexOf(lp);
		
		if (i<0)
			throw new IX_Abort_Exception("Pointer Not Exists");
		
		keyword.add(i, key);
		pointer.add(i+1, rp);
		++numOfKeyword;
		

		int suckPosition = (fhead.Order+1)/2;
		
		int numOfKeyInAnother = numOfKeyword-suckPosition-1;
		numOfKeyword -= numOfKeyInAnother;
		Buffer buf = pfh.GetThisPage(pageNum);
		ByteBuffer bb = buf.contents;
		buf.mark(this.hashCode());
		if (i<suckPosition) {
			byte[] temp = new byte[(fhead.KeywordLength+4)*(suckPosition-i)];
			bb.position(PAGEHEADSIZE+4+(fhead.KeywordLength+4)*i);
			bb.get(temp);
			bb.position(PAGEHEADSIZE+4+(fhead.KeywordLength+4)*(i+1));
			bb.put(temp);
			bb.position(PAGEHEADSIZE+(fhead.KeywordLength+4)*i);
			if (fhead.KeywordType==Keyword.KEYTYPEINT)
				bb.putInt(((IntKeyword)key).getValue());
			else if (fhead.KeywordType==Keyword.KEYTYPESTRING)
				bb.put(((StringKeyword)key).getBytes());
			bb.putInt(rp);
		}
		int preNextPageNum = nextPageNum;
		nextPageNum = node.pageNum;
		bb.putInt(13, nextPageNum);
		bb.putInt(5, numOfKeyword);
		pfh.UnpinPage(pageNum);
		node.SetPrePageNum(pageNum);
		if (preNextPageNum != 0) {
			BPlusTreeNode preNextNode = new BPlusTreeNode(fhead, pfh, preNextPageNum);
			preNextNode.SetPrePageNum(nextPageNum);
			node.SetNextPageNum(preNextPageNum);
			preNextNode = null;
		}
		
		Keyword ret = keyword.remove(suckPosition);
		node.SetPointer(0, pointer.remove(suckPosition+1));
		for (i=0; i<numOfKeyInAnother; ++i)
			node.AddKeyPointerPair(
					new KeywordPointerPair(keyword.remove(suckPosition), 
							pointer.remove(suckPosition+1))
					);
		
		return ret;	
	}
	
	public void DestoryNode() throws PF_Abort_Exception {
		if (fhead.FirstLeafPageNum == this.pageNum)
			fhead.FirstLeafPageNum=this.nextPageNum;
		try {
			pfh.DisposePage(pageNum);
		} catch (PF_Abort_Exception pfe) {
			throw new IX_Abort_Exception(pfe.getMessage());
		}
	}

	public BPlusTreeNode DeleteFromNode(Keyword key, 
			List<BPlusTreeNode> parentList) throws PF_Abort_Exception {
		List<Keyword> keyword = LoadKeyword();
		int i=keyword.indexOf(key);
		if (i<0) 
			throw new IX_Abort_Exception("Key not Exists");
		KeywordPointerPair kpp = RemoveKeyPointerPair(i);
		if (numOfKeyword >= (fhead.Order-1)/2)
			return null;
		
		if (pageNum == fhead.RootPageNum) {
			if (numOfKeyword == 0) {
				DestoryNode();
				return new BPlusTreeNode(fhead, pfh, kpp.pointer);
			}
			return null;
		}
		
		if (this.nextPageNum>0 && 
				parentList.get(parentList.size()-1).isPredecessor(nextPageNum, pageNum))
		{ //try to merge with right node
			BPlusTreeNode rightNode = new BPlusTreeNode(fhead, pfh, nextPageNum);
			return MergeTwoNodes(this, rightNode, parentList);
		}
		if (this.prePageNum>0 &&
				parentList.get(parentList.size()-1).isPredecessor(pageNum, prePageNum))
		{ //try to merge with left node
			BPlusTreeNode leftNode = new BPlusTreeNode(fhead, pfh, prePageNum);
			return MergeTwoNodes(leftNode, this, parentList);
		}
		throw new IX_Abort_Exception("Fatal");
	}
	
	private BPlusTreeNode MergeTwoNodes(
			BPlusTreeNode left,
			BPlusTreeNode right,
			List<BPlusTreeNode> parentList) throws PF_Abort_Exception {
		if (left.numOfKeyword >= (fhead.Order+1)/2 ) { //put rightmost key of left into right
			KeywordPointerPair kpp = left.RemoveKeyPointerPair(left.numOfKeyword-1);
			int leftmostPointer = right.GetPointer(0);
			BPlusTreeNode btnode = new BPlusTreeNode(fhead, pfh, leftmostPointer);
			right.AddKeyPointerPair(0,
					new KeywordPointerPair(btnode.GetKeyword(0), leftmostPointer)
				);
			right.SetPointer(0, kpp.pointer);
			return null;
		}
		if (right.numOfKeyword >= (fhead.Order+1)/2 ) { //put leftmost key of right into left
			int leftmostPointer = right.GetPointer(0);
			KeywordPointerPair kpp = right.RemoveKeyPointerPair(0);
			right.SetPointer(0, kpp.pointer);
			BPlusTreeNode btnode = new BPlusTreeNode(fhead, pfh, leftmostPointer);
			left.AddKeyPointerPair(new KeywordPointerPair(
					btnode.GetKeyword(0), leftmostPointer));
			return null;
		}
		//it has to merge two nodes.
		int leftmostPointer = right.GetPointer(0);
		BPlusTreeNode btnode = new BPlusTreeNode(fhead, pfh, leftmostPointer);
		Keyword minkey = btnode.GetKeyword(0);
		left.AddKeyPointerPair(new KeywordPointerPair(minkey, leftmostPointer));
		for (int i=0; i<right.numOfKeyword; ++i)
			left.AddKeyPointerPair(right.GetKeyPointerPair(i));
		left.nextPageNum = right.nextPageNum;
		right.DestoryNode();
		return parentList.remove(parentList.size()-1).DeleteFromNode(minkey, parentList);
	}
	
/*	public void CombineLeaf(BPlusTreeNode node) {
		if (node.type != LEAF || fhead.KeywordType != node.fhead.KeywordType )
			throw new IX_Abort_Exception();
		Buffer buf = pfh.GetThisPage(pageNum);
		ByteBuffer bb = buf.contents;
		buf.mark(this.hashCode());
		bb.position(PAGEHEADSIZE+numOfKeyword*(fhead.KeywordLength+RID.STORELENGTH));
		if (fhead.KeywordType == LEAF) {
			for (int i=0; i<node.numOfKeyword; ++i) {
				KeywordDataPair kdp = node.GetKeyDataPair(i);
				bb.putInt(((IntKeyword)kdp.key).getValue());
				bb.putInt(kdp.rid.pageNum);
				bb.putInt(kdp.rid.slotNum);
			}
		} else if (fhead.KeywordType == NODE) {
			for (int i=0; i<node.numOfKeyword; ++i) {
				KeywordDataPair kdp = node.GetKeyDataPair(i);
				bb.put(((StringKeyword)kdp.key).getBytes());
				bb.putInt(kdp.rid.pageNum);
				bb.putInt(kdp.rid.pageNum);
				bb.putInt(kdp.rid.slotNum);
			}
		} else
			throw new IX_Abort_Exception();
		numOfKeyword += node.numOfKeyword;
		bb.position(5);
		bb.putInt(numOfKeyword);
		pfh.UnpinPage(pageNum);
	}
*/	
}
